package com.yangli.leecode.mashib.interview;

import java.util.Arrays;
import java.util.HashMap;

/**
 * @Description
 * @Author liyang
 * @Date 2023/4/11 11:31
 */
public class SixtySeven {
    public static void main(String[] args){
        int[] temp = new int[]{0, 2, 1, 3, 6, 8, 7, 5, 4};
        System.out.println(SixtySeven.subarraysWithKDistinct(temp, 3));
    }


    //方法一 搞两个对象，分别记录等于k或者等于k-1的右边界为i的数据，则右边界为i的位置上的k=3数据的 k-（k-1）
    public static int subarraysWithKDistinct(int[] arr, int k){
        int n = arr.length;
        //arr 数据范围在0...n-1之间
        int[] lessarr = new int[n + 1];//存储元素及其频次
        int[] karr = new int[n + 1];
        int lessleft = 0;//左边界
        int kleft = 0;
        int lesskind = 0;//类型
        int kkind = 0;
        int ans = 0;
        for (int i = 0; i < n; i++) {
            if (lessarr[arr[i]] == 0) {
                lesskind++;
            }
            if (karr[arr[i]] == 0) {
                kkind++;
            }
            lessarr[arr[i]]++;
            karr[arr[i]]++;

            if (lesskind == k) {
                if (lessarr[arr[lessleft]] == 1) {
                    lesskind--;
                }
                lessarr[arr[lessleft++]]--;
            }
            if (kkind > k) {
                if (karr[arr[kleft]] == 1) {
                    kkind--;
                }
                karr[arr[kleft++]]--;
            }

            ans += lessleft - kleft;
        }
        return ans;

    }

    //用小于等于K的子数组数量 减去小于等于K-1的子数组数量 就是子数组等于k的数量
    public static int subarraysWithKDistinct2(int[] arr, int k){
        return subarraysWithlessKDistinct(arr, k) - subarraysWithlessKDistinct(arr, k - 1);
    }

    //小于等于K的子数组数量
    public static int subarraysWithlessKDistinct(int[] arr, int k){
        int i = 0;
        int res = 0;
        HashMap<Integer, Integer> count = new HashMap<>();

        for (int j = 0; j < arr.length; ++j) {
            if (count.getOrDefault(arr[j], 0) == 0) {
                k--;
            }
            count.put(arr[j], count.getOrDefault(arr[j], 0) + 1);
            while (k < 0) {
                count.put(arr[j], count.get(arr[j] - 1));
                if (count.get(arr[j]) == 0) {
                    k++;
                }
                i++;
            }
            res = +j - i + 1;
        }
        return res;
    }


    public static int minSplit(int[] arr, int x, int k){
        Arrays.sort(arr);

        int[] needs = new int[arr.length];//间隔数组
        int size = 0;//数组大小
        int split = 1;//默认堆数
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] - arr[i - 1] > k) {
                needs[size++] = arr[i] - arr[i - 1];
                split++;
            }
        }
        if (split == 1 || x == 0 || k == 0) {
            return split;
        }
        Arrays.sort(needs, 0, size);//间隔排序，默认先使用小的间隔
        for (int i = 0; i < arr.length; i++) {
            int need = (arr[i] - 1) / x;//需要的魔法石头数量 ==（a[i]-x）/x向上取整==>由于a/b向上取整==(a+b-1)/b==>（a[i]-1）/x
            if (k >= need) {
                k -= need;
                split--;
            } else {
                break;
            }
        }
        return split;
    }


}
